翻訳と辞書
Words near each other
・ Signpine, Virginia
・ SignPlot
・ Signpost (company)
・ Signpost (disambiguation)
・ Signpost Corner, Isle of Man
・ Signpost to Murder
・ Signs
・ Signed and Sealed in Blood
・ Signed ballot
・ Signed by Katie Price
・ Signed differential mapping
・ Signed distance function
・ Signed Dutch
・ Signed French
・ Signed German
Signed graph
・ Signed Italian
・ Signed Japanese
・ Signed measure
・ Signed Nepali
・ Signed number representations
・ Signed overpunch
・ Signed parish roads in Louisiana
・ Signed Polish
・ Signed Sealed and Delivered
・ Signed sealed delivered
・ Signed Sealed Delivered (album)
・ Signed Spanish
・ Signed to the Streets
・ Signed to the Streets 2


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Signed graph : ウィキペディア英語版
Signed graph
In the area of graph theory in mathematics, a signed graph is a graph in which each edge has a positive or negative sign.
Formally, a signed graph Σ is a pair (''G'', σ) that consists of a graph ''G'' = (''V'', ''E'') and a sign mapping or signature σ from ''E'' to the sign group . The graph may have loops and multiple edges as well as half-edges (with only one endpoint) and loose edges (with no endpoints). Half and loose edges do not receive signs. (In the terminology of the article on graphs, it is a ''multigraph'', but we say ''graph'' because in signed graph theory it is usually unnatural to restrict to simple graphs.)
The sign of a circle (this is the edge set of a simple cycle) is defined to be the product of the signs of its edges; in other words, a circle is positive if it contains an even number of negative edges and negative if it contains an odd number of negative edges. The fundamental fact about a signed graph is the set of positive circles, denoted by ''B''(Σ). A signed graph, or a subgraph or edge set, is called balanced if every circle in it is positive (and it contains no half-edges). Two fundamental questions about a signed graph are: Is it balanced? What is the largest size of a balanced edge set in it? The first question is not difficult; the second is computationally intractable (technically, it is NP-hard).
Signed graphs were first introduced by Harary to handle a problem in social psychology (Cartwright and Harary, 1956). They have been rediscovered many times because they come up naturally in many unrelated areas. For instance, they enable one to describe and analyze the geometry of subsets of the classical root systems. They appear in topological graph theory and group theory. They are a natural context for questions about odd and even cycles in graphs. They appear in computing the ground state energy in the non-ferromagnetic Ising model; for this one needs to find a largest balanced edge set in Σ. They have been applied to data classification in correlation clustering.
==Examples==

* The complete signed graph on ''n'' vertices with loops, denoted by ±''K''''n''o, has every possible positive and negative edge including negative loops, but no positive loops. Its edges correspond to the roots of the root system ''C''''n''; the column of an edge in the incidence matrix (see below) is the vector representing the root.
* The complete signed graph with half-edges, ±''K''''n''', is ±''K''''n'' with a half-edge at every vertex. Its edges correspond to the roots of the root system ''B''''n'', half-edges corresponding to the unit basis vectors.
* The complete signed link graph, ±''K''''n'', is the same but without loops. Its edges correspond to the roots of the root system ''D''''n''.
* An all-positive signed graph has only positive edges. If the underlying graph is ''G'', the all-positive signing is written +''G''.
* An all-negative signed graph has only negative edges. It is balanced if and only if it is bipartite because a circle is positive if and only if it has even length. An all-negative graph with underlying graph ''G'' is written −''G''.
* A signed complete graph has as underlying graph ''G'' the ordinary complete graph ''K''''n''. It may have any signs. Signed complete graphs are equivalent to two-graphs, which are of value in finite group theory. A two-graph can be defined as the class of vertex sets of negative triangles (having an odd number of negative edges) in a signed complete graph.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Signed graph」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.